/*
 * @lc app=leetcode.cn id=5 lang=cpp
 *
 * [5] 最长回文子串
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    string longestPalindrome(string s) {
        int length = s.size();          // 记录字符串的长度
        int begin = 0;
        int maxLength = 1;
        
        if (length < 2) return s;

        vector<vector<int>> dp(length, vector<int>(length));        // dp[i][j] 表示第i到第j子字符串是否为回文串
        
        for (int i = 0; i < length; i++) {
            dp[i][i] = 1;
        }
        
        // 枚举子串长度
        for (int L = 2; L <= length; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < length; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= length) break;
                
                if (s[i] != s[j]) {
                    dp[i][j] = 0;
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1;
                    begin = i;
                }
            }
        }
        
        return s.substr(begin, maxLength);
    }
};
// @lc code=end

